home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / progjour / 1991 / 04 / bstree.c < prev    next >
C/C++ Source or Header  |  1991-06-03  |  3KB  |  98 lines
  1. /* bstree.c */
  2.  
  3. /* This is a simple implementation of a Binary Search Tree.  A tree is a
  4.    special case of the more general structure, the directed graph. A complete
  5.    implementation would require more features, including memory management,
  6.    error handling, and some utility functions.  For example, if one were
  7.    to use a binary search tree in an embedded system application, it would
  8.    be necessary to include a "free list" handling function.  This algorithm
  9.    does not include a capability to keep the nodes of the tree balanced.
  10.    Consequently, a realistic implementation would also include some balancing
  11.    algorithm such as the AVL method.  Using the fundamental ideas of the
  12.    binary search tree, try to implement an "expression tree" */
  13.  
  14.  
  15. #include <stdio.h> 
  16.  
  17. struct NODE 
  18. {
  19.          int    data;
  20.          struct NODE  *left;
  21.          struct NODE  *right;
  22. } ; 
  23.  
  24. #define TREESIZE 100
  25. #define NUL 0
  26.  
  27. void filltree(struct NODE *tree);
  28. void insert (struct NODE *tree, struct NODE *newnode);
  29. void inorder(struct NODE *tree);
  30. void postorder(struct NODE *tree);
  31. int getnumber();
  32.  
  33.  
  34. void main() 
  35. {
  36.     struct NODE numbers[TREESIZE];
  37.     filltree(numbers);     /* insert items into tree */
  38.     inorder(numbers);       /* display tree using inorder traversal */
  39.     postorder(numbers);     /* display tree using postorder traversal */
  40. }
  41.  
  42. void filltree (struct NODE *tree) 
  43. {
  44.     int index = 0;
  45.     int num;
  46.     while ((num=getnumber()) != -1) {
  47.         tree[index].data  = num;
  48.         tree[index].left  = tree[index].right = NUL;
  49.         if (index > 0) insert (tree, &tree[index]);
  50.         index++;
  51.     }
  52. }
  53.  
  54. int getnumber() 
  55. {
  56.     int num;
  57.     printf("\n Enter Positive Integer (-1 to end): ");
  58.     scanf("%d", &num);
  59.     return(num);
  60. }
  61.  
  62. void insert (struct NODE *tree, struct NODE *newnode) 
  63. {
  64.    if (newnode->data < tree->data) {
  65.        if (tree->left == NUL)
  66.           tree->left = newnode;
  67.        else
  68.           insert (tree->left, newnode);
  69.    }
  70.    else {
  71.        if (tree->right == NUL)
  72.           tree->right = newnode;
  73.        else
  74.           insert (tree->right, newnode);
  75.    }
  76. }
  77.  
  78. void inorder (struct NODE *tree)  
  79. {    
  80.         /* notice the placement of printf */
  81.    if (tree->left != NUL)
  82.        inorder (tree->left);        /* call left child again      */
  83.    printf ("%d\n", tree->data);     /* visit the node             */
  84.    if (tree->right != NUL)
  85.        inorder (tree->right);       /* call right child again     */
  86. }
  87.  
  88. void postorder (struct NODE *tree)  
  89. {  
  90.         /* notice the placement of printf */
  91.    if (tree->left != NUL)        /* call left child again       */
  92.        postorder (tree->left);
  93.    if (tree->right != NUL)
  94.        postorder (tree->right);  /* call right child again      */
  95.    printf ("%d\n", tree->data);  /* visit the node              */
  96. }
  97.  
  98.